<!DOCTYPE html>
<html>
    
<head>
    <meta charset="utf-8">
    
    <title>HashMap原理技术知识整理 | ApocalypseBlog</title>
    <canvas id="header_canvas"style="position:absolute;bottom:0"></canvas> 
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">

    

    

    

    

    
<link rel="stylesheet" href="/dist/build.css?v=1.14.0.css">

    <script src="/javascripts/bubble.js"></script>
    <script>
        window.isPost = true
        window.aomori = {
            
            
        }
        window.aomori_logo_typed_animated = false
        window.aomori_search_algolia = false

    </script>
<script>
    ((window.gitter = {}).chat = {}).options = {
      room: 'ApocalypseBlog/Apocalypse'
    };
  </script>
  <script src="https://sidecar.gitter.im/dist/sidecar.v1.js" async defer></script>
<meta name="generator" content="Hexo 5.3.0"></head>
<!--DaoVoice服务http://blog.daovoice.io/-->

    <script>(function (i, s, o, g, r, a, m) {
        i['DaoVoiceObject'] = r;
        i[r] = i[r] ||
          function () {
            (i[r].q = i[r].q || []).push(arguments);
          };
        i[r].l = 1 * new Date();
        a = s.createElement(o);
        m = s.getElementsByTagName(o)[0];
        a.async = 1;
        a.src = g;
        a.charset = 'utf-8';
        m.parentNode.insertBefore(a, m);
      })(window, document, 'script', ('https:' === document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/b00f5052.js", 'daovoice');
      daovoice('init', {
        app_id: "b00f5052",
      });
      daovoice('update');
    </script>
  
<body>

    <div class="container">
    <header class="header">
        <div class="header-type">
            
            <div class="header-type-inner">
                
                    <a class="header-type-title" href="/">ApocalypseBlog</a>
                
    
                
            </div>
        </div>
        <div class="header-menu">
            <div class="header-menu-inner">
                
            </div>
            <div class="header-menu-social">
                
            </div>
        </div>

        <div class="header-menu-mobile">
            <div class="header-menu-mobile-inner" id="mobile-menu-open">
                <i class="icon icon-menu"></i>
            </div>
        </div>
    </header>

    <div class="header-menu-mobile-menu">
        <div class="header-menu-mobile-menu-bg"></div>
        <div class="header-menu-mobile-menu-wrap">
            <div class="header-menu-mobile-menu-inner">
                <div class="header-menu-mobile-menu-close" id="mobile-menu-close">
                    <i class="icon icon-cross"></i>
                </div>
                <div class="header-menu-mobile-menu-list">
                    
                </div>
            </div>
        </div>
    </div>

</div>

    <div class="container">
        <div class="main">
            <section class="inner">
                <section class="inner-main">
                    <div class="post">
    <article id="post-ckk6o6auk00067knygoide9r2" class="article article-type-post" itemscope
    itemprop="blogPost">

    <div class="article-inner">

        
          
        
        
        

        
        <header class="article-header">
            
  
    <h1 class="article-title" itemprop="name">
      HashMap原理技术知识整理
    </h1>
  

        </header>
        

        <div class="article-more-info article-more-info-post hairline">

            <div class="article-date">
  <time datetime="2020-06-11T21:47:26.000Z" itemprop="datePublished">2020-06-12</time>
</div>

            

            

            

        </div>

        <div class="article-entry post-inner-html hairline" itemprop="articleBody">
            <p><img src="http://user-gold-cdn.xitu.io/2020/1/8/16f81686afbf1d6b?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" alt="img"></p>
<p>HashMap涉及的技术点非常多，典型的数据结构和算法有机结合，JDK对HashMap优化变化中不断权衡时间复杂和空间复杂度。</p>
<a id="more"></a>

<h3 id="一-存储结构"><a href="#一-存储结构" class="headerlink" title="一. 存储结构"></a>一. 存储结构</h3><p>1.JDK1.8之前 HashMap = 数组(O(1)）+ 单向链表（O(n)）</p>
<p>2.JDK1.8之后 HashMap = 数组(O(1)）+ 单向链表（O(n)）+ 红黑树(O(log n)</p>
<p><img src="http://user-gold-cdn.xitu.io/2020/1/8/16f815af3de6cbaf?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" alt="HashMap结构图.png"></p>
<p>关于结构的几个关键数字：</p>
<p>1.默认初始化数组容量大小是16。</p>
<p>2.数组扩容刚好是2的次幂。</p>
<p>3.默认的加载因子是0.75。</p>
<p>4.链表长度超过8时将链表转化成红黑树结构。 5.红黑树节点数减少到6的时候退化成链表。</p>
<p>以上几个数字关系，又为什么是上边的几个数字接下来一个个分析。</p>
<h3 id="二-操作原理"><a href="#二-操作原理" class="headerlink" title="二. 操作原理"></a>二. 操作原理</h3><h5 id="1-put储存流程"><a href="#1-put储存流程" class="headerlink" title="1. put储存流程"></a>1. put储存流程</h5><p>①计算桶的位置，根据key的hashcode求出hash值，位置index = hash%length。</p>
<p>②判断是否达到扩容条件，threshold=DEFAULT_INITIAL_CAPACITY * loadFactor（16*0.75=12）大于这个阀门值就需要扩容，否则下一步。</p>
<p>③判断桶位置是否为空，如果为空直接在数据插入数据。如果不为空，下一步。</p>
<p>④判断是链表还是红黑树，链表是否到达转化红黑树，当前链表节点数&lt;=8，插入节点；如果是红黑树插入节点，否则下一步。</p>
<p>⑤链表转化成红黑树，插入节点。</p>
<p>⑥插入节点后计算当前size是否需要扩容，如果大于阀门值需要扩容resize。</p>
<pre><code>/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don&#39;t change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) &#123;
    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) &amp; hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else &#123;
        Node&lt;K,V&gt; e; K k;
        if (p.hash == hash &amp;&amp;
            ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, hash, key, value);
        else &#123;
            for (int binCount = 0; ; ++binCount) &#123;
                if ((e = p.next) == null) &#123;
                    p.next = newNode(hash, key, value, null);
                    if (binCount &gt;= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                &#125;
                if (e.hash == hash &amp;&amp;
                    ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                    break;
                p = e;
            &#125;
        &#125;
        if (e != null) &#123; // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        &#125;
    &#125;
    ++modCount;
    if (++size &gt; threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
&#125;
</code></pre>
<p>以上是JDK1.8的HashMap的get调用关键方法源码。</p>
<h5 id="2-get获取过程"><a href="#2-get获取过程" class="headerlink" title="2. get获取过程"></a>2. get获取过程</h5><p>①计算桶的位置，根据key的hashcode求出hash值，位置index = hash%length。</p>
<p>②无论是数值，链表还是红黑树，for循环判断hash值冲突就比对key是否相等，相等就返回对应的value。</p>
<pre><code>/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node&lt;K,V&gt; getNode(int hash, Object key) &#123;
    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; int n; K k;
    if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp;
        (first = tab[(n - 1) &amp; hash]) != null) &#123;
        if (first.hash == hash &amp;&amp; // always check first node
            ((k = first.key) == key || (key != null &amp;&amp; key.equals(k))))
            return first;
        if ((e = first.next) != null) &#123;
            if (first instanceof TreeNode)
                return ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);
            do &#123;
                if (e.hash == hash &amp;&amp;
                    ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                    return e;
            &#125; while ((e = e.next) != null);
        &#125;
    &#125;
    return null;
&#125;
</code></pre>
<p>以上是JDK1.8的HashMap的put调用关键方法源码。</p>
<h3 id="三-数据结构和算法思考"><a href="#三-数据结构和算法思考" class="headerlink" title="三. 数据结构和算法思考"></a>三. 数据结构和算法思考</h3><h5 id="1-为什么选择数组和链表结构？"><a href="#1-为什么选择数组和链表结构？" class="headerlink" title="1.为什么选择数组和链表结构？"></a>1.为什么选择数组和链表结构？</h5><p>①数组内存连续块分配，效率体现查询更快。HashMap中用作查找数组桶的位置，利用元素的key的hash值对数组长度取模得到。</p>
<p>②链表效率体现增加和删除。HashMap中链表是用来解决hash冲突，增删空间消耗平衡。</p>
<p><strong>扩展：</strong> 为什么不是ArrayList而是使用Node&lt;K,V&gt;[] tab？因为ArrayList的扩容机制是1.5倍扩容，而HashMap扩容是2的次幂。</p>
<h5 id="2-为什么扩容是2次幂，根据key的hashcode再求hash值？"><a href="#2-为什么扩容是2次幂，根据key的hashcode再求hash值？" class="headerlink" title="2.为什么扩容是2次幂，根据key的hashcode再求hash值？"></a>2.为什么扩容是2次幂，根据key的hashcode再求hash值？</h5><h5 id="①key的hash值计算"><a href="#①key的hash值计算" class="headerlink" title="①key的hash值计算"></a>①key的hash值计算</h5><pre><code>static final int hash(Object key) &#123;
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);
&#125;
</code></pre>
<p>代码意思是hash = hashcode的高16位异化低16位，而不是直接hashcode。</p>
<h5 id="②计算桶的位置代码"><a href="#②计算桶的位置代码" class="headerlink" title="②计算桶的位置代码"></a>②计算桶的位置代码</h5><pre><code>index = (n - 1) &amp; hash
</code></pre>
<p><strong>思想：</strong></p>
<p>一是，为了减少hash冲突使用hash%length计算，求模计算保证了得到的结果一定在0-length范围之内。</p>
<p>二是，为了提高运算速度，模运算比不上位运算，当n是2的次幂才满足hash%length == （n-1）&amp;hash。</p>
<p>确定公式中（n-1）符合最优等式，剩下考虑hash值的最优，hash值这个因子考虑影响结果尽可能不冲突。</p>
<p>因为计算速度体现在位运算上，条件n是2的次幂，那么n-1的换算成二进制前边都是连续的0，后边都是连续的1,。比如n=16，则n-1=15，15的二进制1111。hash &amp; 1111 = 只要关注的hash的二进制的最后四位数进行&amp;运算。</p>
<p><img src="http://user-gold-cdn.xitu.io/2020/1/8/16f815af3f39c141?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" alt="（n-1）&amp; length.png"></p>
<p>如上图，最终会与15的二进制进行1111四位运算，如果与key.hashcode进行与运算的话，只要key的hashcode最后四位为0000前边无论是什么都没关系，这样出现相同值的概率高很多。所以，引入hashcode先高低16位进行异或运算，减少hash冲突。</p>
<p><strong>扩展：</strong> hashcode与equals相等判断对比： 两个key的hashcode相等，key不一定equals。 两个key的equals，hashcode一定相等。</p>
<h5 id="3-为什么加载因子为0-75，链表长度大于8转成红黑树？"><a href="#3-为什么加载因子为0-75，链表长度大于8转成红黑树？" class="headerlink" title="3.为什么加载因子为0.75，链表长度大于8转成红黑树？"></a>3.为什么加载因子为0.75，链表长度大于8转成红黑树？</h5><p><strong>思想：</strong></p>
<p>上边问题不是两个独立问题而是相互相关，<strong>目的尽量减少冲突前提提高空间利用率和减少查询成本的折中。</strong></p>
<p>加载因子决定了HashMap的扩容的阀门值，如果桶是16，那么扩容值16* 0.75=12，也就是12的时候就要考虑扩容，还有4个没有被利用到，牺牲的空间。如果加载因子是1，空间利用率高，但是查询速度变慢。</p>
<p><strong>原理：</strong></p>
<p>权衡依据是以上情况符合泊松分布（一种统计与概率学里常见到的离散概率分布，适合于描述单位时间（或空间）内随机事件发生的次数），<strong>用0.75作为加载因子，每个碰撞位置的链表长度超过８个概率非常低，少于千万分之一。</strong></p>
<p><strong>源码说明：</strong></p>
<pre><code> * Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  In
 * usages with well-distributed user hashCodes, tree bins are
 * rarely used.  Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)). The first values are:
 *
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million 
</code></pre>
<p><strong>扩展：</strong></p>
<p>为什么不一开始选择红黑树？</p>
<p>红黑树近乎于平衡二叉树，结构适合均匀分布节点，减少树的深度像链表长度情况。原因主要是插入效率上，红黑树增加节点很可能需要进行左旋，右旋，着色操作，这些时间效率并没有链表形式高。</p>
<h5 id="4-HashMap的key选择"><a href="#4-HashMap的key选择" class="headerlink" title="4.HashMap的key选择"></a>4.HashMap的key选择</h5><p>1）选择不可变的对象，比如字符串或int类型。</p>
<p>2）如果要用一个自定义实体类作为key：</p>
<p>①类添加final修饰符，保证类不被继承。</p>
<p>②保证所有成员变量必须私有，并且加上final修饰。</p>
<p>③不提供改变成员变量的方法，包括setter。</p>
<p>④通过构造器初始化所有成员，进行深拷贝(deep copy)。</p>
<h5 id="5-String类中的hashcode计算"><a href="#5-String类中的hashcode计算" class="headerlink" title="5.String类中的hashcode计算"></a>5.String类中的hashcode计算</h5><pre><code>public int hashCode() &#123;
    int h = hash;
    if (h == 0 &amp;&amp; value.length &gt; 0) &#123;
    char val[] = value;
        for (int i = 0; i &lt; value.length; i++) &#123;
              h = 31 * h + val[i];
          &#125;
          hash = h;
      &#125;
      return h;
&#125;
</code></pre>
<p>哈希计算公式：s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]</p>
<h3 id="四-横向扩展"><a href="#四-横向扩展" class="headerlink" title="四. 横向扩展"></a>四. 横向扩展</h3><h5 id="1-HashMap出现线程问题"><a href="#1-HashMap出现线程问题" class="headerlink" title="1.HashMap出现线程问题"></a>1.HashMap出现线程问题</h5><p>①多线程扩容，引起的死循环问题（jdk1.8中，死循环问题已经解决）。</p>
<p>②多线程put的时候可能导致元素丢失。</p>
<p>③put非null元素后get出来的却是null。</p>
<h5 id="2-使用线程安全Map"><a href="#2-使用线程安全Map" class="headerlink" title="2.使用线程安全Map"></a>2.使用线程安全Map</h5><p>①HashMap并不是线程安全，要实现线程安全可以用Collections.synchronizedMap(m)获取一个线程安全的HashMap。</p>
<p>②CurrentHashMap和HashTable是线程安全的。CurrentHashMap使用分段锁技术，要操作节点先获取段锁，在修改节点。</p>
<h5 id="3-Android提倡使用ArrayMap"><a href="#3-Android提倡使用ArrayMap" class="headerlink" title="3.Android提倡使用ArrayMap"></a>3.Android提倡使用ArrayMap</h5><p>①ArrayMap数据结构是两个数组，一个存放hash值，另一个存放key和value。</p>
<p>②根据key的hash值利用二分查找在hash数组中找出index。</p>
<p>③根据index在key-value数组中对应位置查找，如果不相等认为冲突了，会以key为中心，分别上下展开，逐一查找。</p>
<p>优势，数据量少时（少于1000）相比HashMap更节省内存。劣势，删除和插入时效率要比HashMap要低。</p>

        </div>

    </div>

    

    

    

    

    

    
<nav class="article-nav">
  
    <a href="/2020/06/12/Java%E5%8F%8D%E5%B0%84%E7%9C%9F%E7%9A%84%E5%BE%88%E6%85%A2%E5%90%97/" id="article-nav-newer" class="article-nav-link-wrap">
      <div class="article-nav-caption">下一篇</div>
      <div class="article-nav-title">
        
          Java反射真的很慢吗
        
      </div>
    </a>
  
  
    <a href="/2020/06/12/Rxjava%E5%8F%AA%E7%9C%8B%E8%BF%99%E4%B8%80%E7%AF%87%E6%96%87%E7%AB%A0%E5%B0%B1%E5%A4%9F%E4%BA%86/" id="article-nav-older" class="article-nav-link-wrap">
      <div class="article-nav-caption">上一篇</div>
      <div class="article-nav-title">Rxjava只看这一篇文章就够了</div>
    </a>
  
</nav>


    <section class="share">
        <div class="share-title">分享</div>
        <a class="share-item" target="_blank"
            href="https://twitter.com/share?text=HashMap原理技术知识整理 - ApocalypseBlog&url=http://example.com/2020/06/12/HashMap%E5%8E%9F%E7%90%86%E6%8A%80%E6%9C%AF%E7%9F%A5%E8%AF%86%E6%95%B4%E7%90%86/">
            <box-icon type='logo' name='twitter'></box-icon>
        </a>
        <a class="share-item" target="_blank"
            href="https://www.facebook.com/sharer.php?title=HashMap原理技术知识整理 - ApocalypseBlog&u=http://example.com/2020/06/12/HashMap%E5%8E%9F%E7%90%86%E6%8A%80%E6%9C%AF%E7%9F%A5%E8%AF%86%E6%95%B4%E7%90%86/">
            <box-icon name='facebook-square' type='logo' ></box-icon>
        </a>
        <!-- <a class="share-item" target="_blank"
            href="https://service.weibo.com/share/share.php?title=HashMap原理技术知识整理 - ApocalypseBlog&url=http://example.com/2020/06/12/HashMap%E5%8E%9F%E7%90%86%E6%8A%80%E6%9C%AF%E7%9F%A5%E8%AF%86%E6%95%B4%E7%90%86/&pic=">
            <div class="n-icon n-icon-weibo"></div>
        </a> -->
    </section>

</article>









</div>
                </section>
            </section>

             
            <aside class="sidebar">
            
                
            </aside>
        </div>
    </div>

    <footer class="footer">
    <div class="footer-wave">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1440 320"><path fill="#3c4859" fill-opacity="1" d="M0,160L60,181.3C120,203,240,245,360,240C480,235,600,181,720,186.7C840,192,960,256,1080,261.3C1200,267,1320,213,1380,186.7L1440,160L1440,320L1380,320C1320,320,1200,320,1080,320C960,320,840,320,720,320C600,320,480,320,360,320C240,320,120,320,60,320L0,320Z"></path></svg>
    </div>

    <div class="footer-wrap">
        <div class="footer-inner"> 
            ApocalypseBlog &copy; 2021<br>
            Powered By Hexo · Theme By <a href="https://github.com/lh1me/hexo-theme-aomori" target="_blank">Aomori</a>
        </div>
    </div>

</footer>




<script src="/dist/build.js?1.14.0.js"></script>


<script src="/dist/custom.js?1.14.0.js"></script>









</body>

</html>